{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Number of Maximum Bitwise-OR Subsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countMaxOrSubsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计按位或能得到最大值的子集数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，请你找出 <code>nums</code> 子集 <strong>按位或</strong> 可能得到的<strong> </strong><strong>最大值</strong> ，并返回按位或能得到最大值的 <strong>不同非空子集的数目</strong> 。</p>\n",
    "\n",
    "<p>如果数组 <code>a</code> 可以由数组 <code>b</code> 删除一些元素（或不删除）得到，则认为数组 <code>a</code> 是数组 <code>b</code> 的一个 <strong>子集</strong> 。如果选中的元素下标位置不一样，则认为两个子集 <strong>不同</strong> 。</p>\n",
    "\n",
    "<p>对数组 <code>a</code> 执行 <strong>按位或</strong>&nbsp;，结果等于 <code>a[0] <strong>OR</strong> a[1] <strong>OR</strong> ... <strong>OR</strong> a[a.length - 1]</code>（下标从 <strong>0</strong> 开始）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,1]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>子集按位或能得到的最大值是 3 。有 2 个子集按位或可以得到 3 ：\n",
    "- [3]\n",
    "- [3,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,2,2]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>[2,2,2] 的所有非空子集的按位或都可以得到 2 。总共有 2<sup>3</sup> - 1 = 7 个子集。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,2,1,5]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>子集按位或可能的最大值是 7 。有 6 个子集按位或可以得到 7 ：\n",
    "- [3,5]\n",
    "- [3,1,5]\n",
    "- [3,2,5]\n",
    "- [3,2,1,5]\n",
    "- [2,5]\n",
    "- [2,1,5]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 16</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-number-of-maximum-bitwise-or-subsets](https://leetcode.cn/problems/count-number-of-maximum-bitwise-or-subsets/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-number-of-maximum-bitwise-or-subsets](https://leetcode.cn/problems/count-number-of-maximum-bitwise-or-subsets/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1]', '[2,2,2]', '[3,2,1,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        # 1 <= nums.length <= 16\n",
    "        # 1 <= nums[i] <= 10^5\n",
    "        # 这数据范围，直接暴力\n",
    "        cnt = 0\n",
    "        n = len(nums)\n",
    "        target = reduce(lambda x, y: x | y, nums)\n",
    "        \n",
    "        for s in range(2**n):\n",
    "            v = 0\n",
    "            for d in range(n):\n",
    "                if s >> d & 1:\n",
    "                    v |= nums[d]\n",
    "            cnt += v == target\n",
    "        \n",
    "        return cnt\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        for x in nums:\n",
    "            res|=x\n",
    "        ans=0\n",
    "        n=len(nums)\n",
    "        for i in range(1,1<<n):\n",
    "            now=0\n",
    "            for j in range(0,n):\n",
    "                if i>>j&1:\n",
    "                    now|=nums[j]\n",
    "            if now==res:ans+=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        maxOr, cnt = 0, 0\n",
    "        for i in range(1, 1 << len(nums)):\n",
    "            orVal = reduce(or_, (num for j, num in enumerate(nums) if (i >> j) & 1), 0)\n",
    "            if orVal > maxOr:\n",
    "                maxOr, cnt = orVal, 1\n",
    "            elif orVal == maxOr:\n",
    "                cnt += 1\n",
    "        return cnt\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/count-number-of-maximum-bitwise-or-subsets/solutions/1335667/tong-ji-an-wei-huo-neng-de-dao-zui-da-zh-r6zd/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "    n =len(nums)\n",
    "    mx =0\n",
    "    ans=0\n",
    "    for i in nums:\n",
    "      mx |= i\n",
    "    print(mx)\n",
    "    for i in range(1,2**n):\n",
    "      s=str(bin(i))\n",
    "      s=s[2:]\n",
    "      t =len(s)\n",
    "      s=''.join(['0' for p in range(n-t)])+s\n",
    "      #print(s)\n",
    "      rt =0\n",
    "      for i,c in enumerate(s):\n",
    "        if c=='1':\n",
    "          rt|=nums[i]\n",
    "      if rt==mx :\n",
    "        ans+=1\n",
    "    return ans\n",
    "        \n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mp = defaultdict(int)\n",
    "        for i in range(1, 1 << len(nums)):\n",
    "            s = 0\n",
    "            for j in range(len(nums)):\n",
    "                if i >> j & 1: s |= nums[j]\n",
    "            mp[s] += 1\n",
    "        return mp[max(mp)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        m, n = 0, len(nums)\n",
    "        for num in nums:\n",
    "            m |= num\n",
    "        \n",
    "        def dfs(idx, val):\n",
    "            if idx == n: return int(val == m)\n",
    "            return dfs(idx + 1, val | nums[idx]) + dfs(idx + 1,val)\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        target = reduce(or_, nums)\n",
    "        n = len(nums)\n",
    "        def dfs(i, v):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            v2 = v | nums[i]\n",
    "            return (v2 == target) + dfs(i + 1, v2) + dfs(i + 1, v)\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        maxOr, cnt = 0,0\n",
    "        def dfs(pos,orVal):\n",
    "            if pos==len(nums):\n",
    "                nonlocal maxOr,cnt\n",
    "                if orVal > maxOr:\n",
    "                    maxOr,cnt = orVal,1\n",
    "                elif orVal == maxOr:\n",
    "                    cnt += 1\n",
    "                return\n",
    "            dfs(pos+1, orVal | nums[pos])\n",
    "            dfs(pos+1, orVal)\n",
    "        dfs(0,0)\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        max_or = 0\n",
    "        for num in nums:\n",
    "            max_or |= num\n",
    "\n",
    "        def backtrack(start, current_or):\n",
    "            if start == len(nums):\n",
    "                return 1 if current_or == max_or else 0\n",
    "            return backtrack(start + 1, current_or | nums[start]) + backtrack(start + 1, current_or)\n",
    "\n",
    "        return backtrack(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        val, cnt = 0, 0\n",
    "        for i in range(1, 1 << len(nums)):\n",
    "            tmp = functools.reduce(operator.or_, (x for j, x in enumerate(nums) if (i >> j) & 1), 0)\n",
    "            if tmp > val:\n",
    "                val, cnt = tmp, 1\n",
    "            elif tmp == val:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                pass\n",
    "\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        ans=[0]\n",
    "        self.res=0\n",
    "        for i in nums:\n",
    "            self.res|=i \n",
    "        n=len(nums)\n",
    "        def backtrack(i,s):\n",
    "            if i>=n:\n",
    "                return 0\n",
    "            temp=s|nums[i]\n",
    "            if temp==self.res:\n",
    "                ans[0]+=1\n",
    "            backtrack(i+1,temp)\n",
    "            backtrack(i+1,s)\n",
    "        backtrack(0,0)\n",
    "        return ans[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        def helper(li):\n",
    "            if not li: return -1\n",
    "            if len(li) == 1: return li[0]\n",
    "            val = li[0]\n",
    "            for i in range(1, len(li)):\n",
    "                val |= li[i]\n",
    "            return val\n",
    "\n",
    "        def dfs(begin, path):\n",
    "            nonlocal res\n",
    "            if helper(path) == max_val:\n",
    "                res +=1\n",
    "            for i in range(begin, n):\n",
    "                dfs(i+1, path+[nums[i]])\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        max_val = helper(nums)\n",
    "        dfs(0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        # 方法1、二进制写法\n",
    "        n = len(nums)\n",
    "        maxNum = 0\n",
    "        num = 0\n",
    "        for mask in range(1,1 << n):\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i):\n",
    "                    res |= nums[i]\n",
    "            if res >= maxNum:\n",
    "                if res > maxNum:\n",
    "                    maxNum = res\n",
    "                    num = 1\n",
    "                else:\n",
    "                    num += 1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        #回溯算法+位运算\n",
    "        max_or,cnt=0,0\n",
    "        def dfs(pos,val):\n",
    "            nonlocal max_or,cnt\n",
    "            if pos==len(nums):\n",
    "                if val>max_or:\n",
    "                    max_or,cnt=val,1\n",
    "                elif val==max_or:\n",
    "                    cnt+=1\n",
    "                return \n",
    "            #不选\n",
    "            dfs(pos+1,val)\n",
    "            #选\n",
    "            dfs(pos+1,val|nums[pos])\n",
    "        dfs(0,0)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        mask=1<<n\n",
    "        ans=0\n",
    "        m_v=0\n",
    "        for x in nums:\n",
    "            m_v|=x\n",
    "        for s in range(mask):\n",
    "            res=0\n",
    "            for i in range(n):\n",
    "               if (s>>i)&1==1:\n",
    "                   res|=nums[i]\n",
    "            if res==m_v:\n",
    "                ans+=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        #暴力解法\n",
    "        # m_v=0\n",
    "        # for x in nums:\n",
    "        #     m_v|=x\n",
    "        # @cache\n",
    "        # def dfs(i,res):\n",
    "        #     if i<0:\n",
    "        #         return 1 if res==m_v else 0\n",
    "            \n",
    "        #     return dfs(i-1,res)+dfs(i-1,res|nums[i])\n",
    "        # return dfs(len(nums)-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        # 找出最大值\n",
    "        mx = 0\n",
    "        for num in nums:\n",
    "            mx |= num\n",
    "        # 遍历所有子集，看是否要计算在内\n",
    "        def dfs(i, n, nums, curValue, mx):\n",
    "            if i == n:\n",
    "                return 1 if curValue == mx else 0\n",
    "            a = dfs(i+1, n, nums, curValue|nums[i], mx)\n",
    "            b = dfs(i+1, n, nums, curValue, mx)\n",
    "            return a+b\n",
    "        return dfs(0, nums.__len__(), nums, 0, mx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        mx = 32\n",
    "        n = len(nums)\n",
    "        target = reduce(lambda x,y:x|y,nums)\n",
    "        ans = 0\n",
    "        for i in range(1,2**n):\n",
    "            cur = 0\n",
    "            for j in range(n):\n",
    "                if (i>>j)&1:\n",
    "                    cur |= nums[j]\n",
    "            if cur == target:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ceil = reduce(or_, nums)\n",
    "        ans = 0\n",
    "        for i in range(1, 1<<n):\n",
    "            lst = [nums[j] for j in range(n) if i&(1<<j)]\n",
    "            if reduce(or_, lst) == ceil:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        mx = 32\n",
    "        n = len(nums)\n",
    "        target = -inf\n",
    "        ans = 0\n",
    "        for i in range(2**n-1,0,-1):\n",
    "            cur = 0\n",
    "            for j in range(n):\n",
    "                if (i>>j)&1:\n",
    "                    cur |= nums[j]\n",
    "            if target == -inf:\n",
    "                target = cur\n",
    "            if cur == target:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        max_or, count = 0, 0\n",
    "        def search(t_or, num_list):\n",
    "            nonlocal max_or, count\n",
    "            if t_or > max_or:\n",
    "                max_or = t_or\n",
    "                count = 1\n",
    "            elif t_or == max_or:\n",
    "                count += 1\n",
    "            for i in range(len(num_list)):\n",
    "                temp = t_or | num_list[i]\n",
    "                search(temp, num_list[i + 1:])\n",
    "        search(0, nums)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        max_or = 0\n",
    "        for num in nums:\n",
    "            max_or |= num\n",
    "\n",
    "        def backtrack(start, current_or):\n",
    "            if start == len(nums):\n",
    "                return 1 if current_or == max_or else 0\n",
    "            return backtrack(start + 1, current_or | nums[start]) + backtrack(start + 1, current_or)\n",
    "\n",
    "        return backtrack(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        maxOr, cnt = 0, 0\n",
    "        def dfs(pos: int, orVal: int) -> None:\n",
    "            if pos == len(nums):\n",
    "                nonlocal maxOr, cnt\n",
    "                if orVal > maxOr:\n",
    "                    maxOr, cnt = orVal, 1\n",
    "                elif orVal == maxOr:\n",
    "                    cnt += 1\n",
    "                return\n",
    "            dfs(pos + 1, orVal | nums[pos])\n",
    "            dfs(pos + 1, orVal)\n",
    "        dfs(0, 0)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        mask=1<<n\n",
    "        ans=0\n",
    "        m_v=0\n",
    "        for x in nums:\n",
    "            m_v|=x\n",
    "        for s in range(mask):\n",
    "            res=0\n",
    "            for i in range(n):\n",
    "               if (s>>i)&1==1:\n",
    "                   res|=nums[i]\n",
    "            if res==m_v:\n",
    "                ans+=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        #暴力解法\n",
    "        # m_v=0\n",
    "        # for x in nums:\n",
    "        #     m_v|=x\n",
    "        # @cache\n",
    "        # def dfs(i,res):\n",
    "        #     if i<0:\n",
    "        #         return 1 if res==m_v else 0\n",
    "            \n",
    "        #     return dfs(i-1,res)+dfs(i-1,res|nums[i])\n",
    "        # return dfs(len(nums)-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        max_or = 0\n",
    "        for num in nums:\n",
    "            max_or |= num\n",
    "\n",
    "        def backtrack(start, current_or):\n",
    "            if start == len(nums):\n",
    "                return 1 if current_or == max_or else 0\n",
    "            return backtrack(start + 1, current_or | nums[start]) + backtrack(start + 1, current_or)\n",
    "\n",
    "        result = backtrack(0, 0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        #回溯算法+位运算\n",
    "        max_or,cnt=0,0\n",
    "        def dfs(pos,val):\n",
    "            nonlocal max_or,cnt\n",
    "            if pos==len(nums):\n",
    "                if val>max_or:\n",
    "                    max_or,cnt=val,1\n",
    "                elif val==max_or:\n",
    "                    cnt+=1\n",
    "                return \n",
    "            #不选\n",
    "            dfs(pos+1,val)\n",
    "            #选\n",
    "            dfs(pos+1,val|nums[pos])\n",
    "        dfs(0,0)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        mask=1<<n\n",
    "        ans=0\n",
    "        m_v=0\n",
    "        for x in nums:\n",
    "            m_v|=x\n",
    "        for s in range(mask):\n",
    "            res=0\n",
    "            for i in range(n):\n",
    "               if (s>>i)&1==1:\n",
    "                   res|=nums[i]\n",
    "            if res==m_v:\n",
    "                ans+=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        #暴力解法\n",
    "        # m_v=0\n",
    "        # for x in nums:\n",
    "        #     m_v|=x\n",
    "        # @cache\n",
    "        # def dfs(i,res):\n",
    "        #     if i<0:\n",
    "        #         return 1 if res==m_v else 0\n",
    "            \n",
    "        #     return dfs(i-1,res)+dfs(i-1,res|nums[i])\n",
    "        # return dfs(len(nums)-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        ret = 0\n",
    "        n = len(nums)\n",
    "        for i in range(1, 1 << n):\n",
    "            k = cnt = 0\n",
    "            for j in range(n):\n",
    "                if i & 1 << j:\n",
    "                    k |= nums[j]\n",
    "                    cnt += 1\n",
    "            if k > ret:\n",
    "                ret, retcnt = k, 1\n",
    "            elif k == ret:\n",
    "                retcnt += 1\n",
    "        return retcnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        target = reduce(or_, nums)\n",
    "        ans = 0\n",
    "        def dfs(k, val):\n",
    "            nonlocal ans\n",
    "            if k == n:\n",
    "                return\n",
    "            for i in range(k, n):\n",
    "                cur = val | nums[i]\n",
    "                if cur == target:\n",
    "                    ans += 1\n",
    "                dfs(i + 1, cur)\n",
    "        dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "        n = len(nums)\n",
    "        for i in range(1, n + 1):\n",
    "            arr = itertools.combinations(nums, i)\n",
    "            for part in arr:\n",
    "                tmp = part[0]\n",
    "                for k in range(1, len(part)):\n",
    "                    tmp |= part[k]\n",
    "                if tmp > ans:\n",
    "                    ans = tmp\n",
    "                    cnt = 1\n",
    "                elif tmp == ans:\n",
    "                    cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        max_or = 0\n",
    "        for num in nums:\n",
    "            max_or |= num\n",
    "\n",
    "        def backtrack(start, current_or):\n",
    "            if start == len(nums):\n",
    "                return 1 if current_or == max_or else 0\n",
    "            return backtrack(start + 1, current_or | nums[start]) + backtrack(start + 1, current_or)\n",
    "\n",
    "        result = backtrack(0, 0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        maxOr, cnt = 0,0\n",
    "        def dfs(index, orValue):\n",
    "            if index==len(nums):\n",
    "                nonlocal maxOr,cnt\n",
    "                if orValue > maxOr:\n",
    "                    maxOr = orValue\n",
    "                    cnt = 1\n",
    "                elif orValue == maxOr:\n",
    "                    cnt += 1\n",
    "                return\n",
    "\n",
    "            dfs(index+1, orValue | nums[index])\n",
    "            dfs(index+1, orValue)\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        maxor, cnt = 0, 0\n",
    "        def dfs(pos: int, orval: int) :\n",
    "            if pos == len(nums) :\n",
    "                nonlocal maxor, cnt\n",
    "                if orval > maxor:\n",
    "                    maxor, cnt = orval, 1\n",
    "                elif orval == maxor:\n",
    "                    cnt += 1\n",
    "                return\n",
    "            dfs(pos + 1, orval | nums[pos])\n",
    "            dfs(pos + 1, orval)\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        target = reduce(or_, nums)\n",
    "        ans = 0\n",
    "        def dfs(k, val):\n",
    "            nonlocal ans\n",
    "            if k == n:\n",
    "                if val == target:\n",
    "                    ans += 1\n",
    "                return\n",
    "            dfs(k + 1, val | nums[k])\n",
    "            dfs(k + 1, val)\n",
    "        dfs(0, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        sm = 0\n",
    "        for x in nums:\n",
    "            sm |= x\n",
    "        ans = 0\n",
    "        def dfs(i, tot):\n",
    "            nonlocal ans\n",
    "            if i == n:\n",
    "                ans += tot == sm\n",
    "                return\n",
    "            dfs(i+1, tot)\n",
    "            dfs(i+1, tot | nums[i])\n",
    "        dfs(0, 0)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        a = 0\n",
    "        for j in nums:\n",
    "            a = a|j\n",
    "        n = len(nums)\n",
    "        def dfs(j, pre):\n",
    "            if j==n:\n",
    "                if pre==a:\n",
    "                    self.ans += 1\n",
    "                return \n",
    "            dfs(j+1, pre|nums[j])\n",
    "            dfs(j+1, pre)\n",
    "        dfs(0, 0)\n",
    "        return self.ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        target = reduce(or_, nums)\n",
    "        ans = 0\n",
    "        def dfs(k, val):\n",
    "            nonlocal ans\n",
    "            if k == n:\n",
    "                return\n",
    "            for i in range(k, n):\n",
    "                if (val | nums[i]) == target:\n",
    "                    ans += 1\n",
    "                dfs(i + 1, val | nums[i])\n",
    "        dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\r\n",
    "        oMax = 0\r\n",
    "        for n in nums:\r\n",
    "            oMax |= n\r\n",
    "        ans = 0\r\n",
    "        n = len(nums)\r\n",
    "        for i in range(1, 1 << n):\r\n",
    "            o = 0\r\n",
    "            for j in range(n):\r\n",
    "                if i & (1 << j):\r\n",
    "                    o |= nums[j]\r\n",
    "            if o == oMax:\r\n",
    "                ans += 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        d = defaultdict(int)\n",
    "        for i in range(1, 1 << n):\n",
    "            cnt = 0\n",
    "            for j in range(n):\n",
    "                if i & (1 << j) != 0:\n",
    "                    cnt |= nums[j]\n",
    "            d[cnt] += 1\n",
    "        return d[max(d.keys())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        sub = list()\n",
    "\n",
    "        def cal(nums):\n",
    "            result = 0\n",
    "            for num in nums:\n",
    "                result = result | num\n",
    "            return result\n",
    "\n",
    "        result = 0\n",
    "        count = 0\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal result, count\n",
    "            if i == n:\n",
    "                tmp = cal(sub)\n",
    "                if tmp > result:\n",
    "                    result = tmp\n",
    "                    count = 1\n",
    "                elif tmp == result:\n",
    "                    count += 1\n",
    "                return\n",
    "            dfs(i+1)\n",
    "            sub.append(nums[i])\n",
    "            dfs(i+1)\n",
    "            sub.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dic = defaultdict(int)\n",
    "        def dfs(index,s):\n",
    "            if index == n:\n",
    "                #print(stack,s)\n",
    "                dic[s] += 1\n",
    "                return \n",
    "            dfs(index+1,s|nums[index])\n",
    "            dfs(index+1,s)\n",
    "        dfs(0,0)\n",
    "        res = [0,0]\n",
    "        for k,v in dic.items():\n",
    "            if k > res[0]:\n",
    "                res = [k,v]\n",
    "        return res[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "\n",
    "        dp = {}\n",
    "        def dfs(loc, eor):\n",
    "            if loc < 0:\n",
    "                dp[eor] = dp.get(eor, 0) + 1\n",
    "                return \n",
    "            dfs(loc-1, eor) # 要\n",
    "            dfs(loc-1, eor|nums[loc]) # 不要\n",
    "        dfs(len(nums)-1, 0)\n",
    "        ans = 0\n",
    "        for k, v in dp.items():\n",
    "            ans = max(ans, v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        mask=1<<n\n",
    "        f=[0]*mask\n",
    "        ans=0\n",
    "        m_v=0\n",
    "        for x in nums:\n",
    "            m_v|=x\n",
    "        for s in range(mask):\n",
    "            res=0\n",
    "            for i in range(n):\n",
    "               if (s>>i)&1==1:\n",
    "                   res|=nums[i]\n",
    "            if res==m_v:\n",
    "                ans+=1\n",
    "                   \n",
    "                   \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        #暴力解法\n",
    "        # m_v=0\n",
    "        # for x in nums:\n",
    "        #     m_v|=x\n",
    "        # @cache\n",
    "        # def dfs(i,res):\n",
    "        #     if i<0:\n",
    "        #         return 1 if res==m_v else 0\n",
    "            \n",
    "        #     return dfs(i-1,res)+dfs(i-1,res|nums[i])\n",
    "        # return dfs(len(nums)-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        m_v=0\n",
    "        for x in nums:\n",
    "            m_v|=x\n",
    "        @cache\n",
    "        def dfs(i,res):\n",
    "            if i<0:\n",
    "                return 1 if res==m_v else 0\n",
    "            \n",
    "            return dfs(i-1,res)+dfs(i-1,res|nums[i])\n",
    "        return dfs(len(nums)-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        # 暴力:先找到子集，再统计 因nums.length <= 16，用O(2^n)的方法可以通过\n",
    "        res = [0]\n",
    "        for i in range(len(nums)):\n",
    "            res += [nums[i]|j for j in res]\n",
    "            #print(res)\n",
    "        return res.count(max(res))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        res = [0]\n",
    "        for i in range(len(nums)):\n",
    "            res += [nums[i] | j for j in res]\n",
    "        return res.count(max(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "class Solution:\n",
    "    def countMaxOrSubsets(self, nums: List[int]) -> int:\n",
    "        d = {}\n",
    "        for i in range(1, len(nums)+1):\n",
    "            # 找出所有单词的组合\n",
    "            combinations = itertools.combinations(nums, i)\n",
    "            combinations = list(combinations)\n",
    "            # print(combinations)\n",
    "            for c in combinations:\n",
    "                t = 0\n",
    "                for cc in c:\n",
    "                    t |= cc\n",
    "                # print(t)\n",
    "                if t not in d:\n",
    "                    d[t] = 1\n",
    "                else:\n",
    "                    d[t] += 1\n",
    "        # print(d)\n",
    "        r = 0\n",
    "        for k in d:\n",
    "            if d[k] > r:\n",
    "                r = d[k]\n",
    "        return r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
